// Board.cpp: implementation of the CBoard class.
//
//////////////////////////////////////////////////////////////////////

#include "Common.h"
#include "Board.h"
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CBoard::CBoard(int width, int height)
:
	m_bFindMultipleSolutions(false)
{
	width = 4; height = 4;
	
	int squareSize = width * height;

	m_pBoard = (tCell*) malloc(squareSize  * sizeof(tCell));
	m_pLeftPane	= (int*) malloc(squareSize * sizeof(int));
	m_pTopPane	= (int*) malloc(squareSize * sizeof(int));

	m_Width = width;
	m_Height = height;


	Init();

//     1  2  4
//   -+--------
// 2 1|XXXX  XX
//   3|  XXXXXX
//   2|    XXXX
//   1|      XX

	SetLeftPane(0, 0, 2);
	SetLeftPane(0, 1, 1);
	SetLeftPane(1, 0, 3);
	SetLeftPane(2, 0, 2);
	SetLeftPane(3, 0, 1);

	SetTopPane(0, 0, 1);
	SetTopPane(1, 0, 2);
	SetTopPane(2, 0, 2);
	SetTopPane(3, 0, 4);

	tCell c;
	c.status = FILLED;
	SetCell(0, 0, &c);
//	SetCell(1, 0, &c);
	SetCell(2, 0, &c);
}

void CBoard::Init()
{
	int x, y;

	tCell emptyCell;

	emptyCell.status = EMPTY;

	for(y = 0; y < m_Height; y++)
	{
		for(x = 0; x < m_Width; x++)
		{
			SetCell(x, y, &emptyCell);
			SetTopPane(x, y, 0);
			SetLeftPane(y, x, 0);
		}
	}

}

CBoard::~CBoard()
{
	free(m_pTopPane);
	free(m_pLeftPane);
	free(m_pBoard);

}

tCell* CBoard::GetCell(int x, int y)
{
	assert(x < m_Width);
	assert(y < m_Height);

	return m_pBoard + (y * m_Width + x);
}

void CBoard::SetCell(int x, int y, tCell* pCell)
{
	*(m_pBoard + (y * m_Width + x)) = *pCell;
}

int CBoard::GetLeftPane(int y, int x)
{
	return *(m_pLeftPane + (y * m_Width + x));
}

void CBoard::SetLeftPane(int y, int x, int N)
{
	*(m_pLeftPane + (y * m_Width + x)) = N;
}


int CBoard::GetTopPane(int x, int y)
{
	return *(m_pTopPane + (x * m_Height + y));
}

void CBoard::SetTopPane(int x, int y, int N)
{
	*(m_pTopPane + (x * m_Height + y)) = N;
}


int CBoard::ValidateRow(int y)
{
	int paneX = 0;
	int boardX = 0;
	int n, res = 1;
	while((n = GetLeftPane(y, paneX++)) > 0)
	{
		// Turing machine :))
		// go while empty
		while(boardX < m_Width && GetCell(boardX, y)->status == EMPTY) boardX++;

		// go exactly n non-empty
		int expectedBX = boardX + n;
		while(boardX < m_Width && GetCell(boardX, y)->status == FILLED) boardX++;

		// check
		if(boardX != expectedBX){ res = 0; break;}

	}

	return res;
}

int CBoard::ValidateCol(int x)
{
	int paneY = 0;
	int boardY = 0;
	int n, res = 1;
	while((n = GetTopPane(x, paneY++)) > 0)
	{
		// Turing machine :))
		// go while empty
		while(boardY < m_Height && GetCell(x, boardY)->status == EMPTY) boardY++;

		// go exactly n non-empty
		int expectedBY = boardY + n;
		while(boardY < m_Height && GetCell(x, boardY)->status == FILLED) boardY++;

		// check
		if(boardY != expectedBY) { res = 0; break;}

	}

	return res;
}


int CBoard::CombineRow(int rowY)
{
	if(rowY < m_Height)
	{
		// run all combinations
		// calculate N of slices
		int N, slN = 0; int pos = 0; // currently can do it w/o pos
		int sumLen = 0;
		while(pos < m_Width && (N = GetLeftPane(rowY, pos++)) > 0)
		{slN++; sumLen += N;}
		int n = 0, x, i;

		int* pMaxIdx = (int*) malloc(slN * sizeof(int));
		int* pMinIdx = (int*) malloc(slN * sizeof(int));
		int* pCurIdx = (int*) malloc(slN * sizeof(int));

		int op = m_Width - (sumLen + slN - 1);
		int currIdx = 0;

		for(i = 0; i < slN; i++)
		{
			pMinIdx[i] = currIdx;
			pMaxIdx[i] = currIdx + op;
			pCurIdx[i] = currIdx;
			currIdx += GetLeftPane(rowY, i) + 1;
		}

		assert((currIdx + op - 1) == m_Width); 


		int marker = slN - 1;

		do 
		{
			// "draw" current position
			tCell empty; empty.status = EMPTY;
			tCell filled; filled.status = FILLED;

			//clear entire row
			for (x = 0; x < m_Width; x++) SetCell(x, rowY, &empty);

			for(i = 0; i < slN; i++)
			{
				// draw slice starting from pCurIdx, len according to index
				for(x = pCurIdx[i]; x < (pCurIdx[i] + GetLeftPane(rowY, i)); x++) SetCell(x, rowY, &filled);
			}

			// check current position
			CombineRow(rowY+1);
			
			// update position
			if(pCurIdx[marker] == pMaxIdx[marker] && (marker > 0))
			{
				marker--;
			}

			pCurIdx[marker]++;
			for(i = marker+1; i < slN; i++) pCurIdx[i] = pCurIdx[i-1] + GetLeftPane(rowY, i-1) + 1;

		} while(pCurIdx[0] <= pMaxIdx[0]);

		
//		for(x = 0; n < slN; n++)
//		{
//			for(x = 
//
//		}

	}
	else
	{
		int x = 0;
		int res;

		printf("Proposed:\n");
		PrintBoard();

		// check
		while(x < m_Width && (res = ValidateCol(x++)));
		if(res)
		{
			
			printf("Approved!\n");
			if(!m_bFindMultipleSolutions)
			{
				return 1;
			}
		}
		printf("Rejected!\n");
	}

	return 0;
}


int CBoard::Solve()
{
	return CombineRow(0);
}



void CBoard::PrintBoard()
{
	// find longest left and top pane row
	int ll = 0;
	int lt = 0;
	int i;

	// left
	for(i = 0; i < m_Height; i++)
	{
		int pos = 0; while(m_pLeftPane[pos] > 0) pos++;
		if(ll < pos) ll = pos;
	}

	// top
	for(i = 0; i < m_Width; i++)
	{
		int pos = 0; while(m_pTopPane[pos] > 0) pos++;
		if(lt < pos) lt = pos;
	}

	printf("Longest top: %d, left: %d\n\n\n", lt, ll);

	int x, y;

	for(y = 0; y < lt; y++)
	{
		for(i = 0; i < ll; i++) printf("   "); printf("|");

		for(x = 0; x < m_Width; x++)
		{
			printf("%2d", GetTopPane(x, y)); printf(" ");
		}
		printf("\n");
	}

	for(i = 0; i < ll; i++) printf("---");
	printf("+");
	for(i = 0; i < m_Width; i++) printf("---");
	printf("\n");


	for(y = 0; y < m_Height; y++)
	{
		for(x = 0; x < ll; x++)
		{
			int N = GetLeftPane(y, x);
			if(N) printf("%2d", N); else printf("  ");
			printf(" ");
		}
		printf("|");
		
		for(x = 0; x < m_Width; x++)
		{
			tCell* pCell = GetCell(x, y);
			if(pCell->status == EMPTY) printf(" . ");
			if(pCell->status == FILLED) printf(" X ");
		}

		printf("\n");

	}

	printf("\n");

	ValidateRow(0);
	ValidateCol(0);

}